The majority of patients diagnosed with melanoma present with thin lesions and generally these patients have a good prognosis. However, 5% of patients with early melanoma (<1 mm thick) will have recurrence and die within 10 years, despite no evidence of local or metastatic spread at the time of diagnosis. Thus, there is a need for additional prognostic markers to help identify those patients that may be at risk of recurrent disease. Many studies and several meta-analyses have compared gene and protein expression in melanocytes, naevi, primary, and metastatic melanoma in an attempt to find informative prognostic markers for these patients. However, although a large number of putative biomarkers have been described, few of these molecules are informative when used in isolation. The best approach is likely to involve a combination of molecules. We believe one approach could be to analyze the expression of a group of interacting proteins that regulate different aspects of the metastatic pathway. This is because a primary lesion expressing proteins involved in multiple stages of metastasis may be more likely to lead to secondary disease than one that does not. This review focuses on five putative biomarkers – melanoma cell adhesion molecule (MCAM), galectin-3 (gal-3), matrix metalloproteinase 2 (MMP-2), chondroitin sulfate proteoglycan 4 (CSPG4), and paired box 3 (PAX3). The goal is to provide context around what is known about the contribution of these biomarkers to melanoma biology and metastasis. Although each of these molecules have been independently identified as likely biomarkers, it is clear from our analyses that each are closely linked with each other, with intertwined roles in melanoma biology.